package com.leetcode.search.bfs;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Dennis Li
 * @date 2020/7/25 16:13
 */
public class ShortestPathBinaryMatrix_1091 {

    public int shortestPathBinaryMatrix(int[][] grid) {
        // 先决判断
        if (grid == null || grid.length == 0 || grid[0].length == 0) return -1;
        int[][] directions = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}};
        Queue<int[]> queue = new LinkedList<>();
        int high = grid.length, width = grid[0].length;
        queue.offer(new int[]{0, 0});
        int len = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            len++;
            // 经典例题 ：周边延伸决策问题
            // 需要先消耗完当前队列的所有1才可以
            while (size-- > 0) {
                int[] now = queue.poll();
                // 有之前为1的部分
                if (grid[now[0]][now[1]] == 1) continue;
                if (now[0] == width - 1 && now[1] == high - 1) return len;
                grid[now[0]][now[1]] = 1;
                for (int[] direction : directions) {
                    int x = now[0] + direction[0], y = now[1] + direction[1];
                    // 不超界, 并且不选为1的部分
                    if (x >= 0 && x < width && y >= 0 && y < high && grid[x][y] != 1)
                        queue.offer(new int[]{x, y});
                }
            }
        }
        return -1;
    }

}
